﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DK.Sort
{
    public class QuickSort : ISort
    {
        public void Sort(int[] array)
        {
            Sort(array, 0, array.Length - 1);
        }

        public void Sort(int[] array, int start, int end) 
        {
            //结束条件
            if (start >= end) 
            {
                return;
            }

            //递归前
            var mid = Group(array, start, end);

            //递归
            Sort(array, start, mid - 1);
            Sort(array, mid + 1, end);
        }

        public int Group(int[] array, int start, int end)
        {
            //双指针排查法
            //right找比基准值小的元素，找到后left找比基准值大的元素
            //查找完毕到后两交换位置

            var left = start;
            var right = end + 1;
            var key = start;

            while (left < right)
            {
                --right;
                if (array[right] < array[key])
                {
                    while (left < right)
                    {
                        if (array[left] > array[key])
                        {
                            ISort.Transfrom(array, left, right);
                            break;
                        }
                        left++;
                    }
                }
            }

            ISort.Transfrom(array, key, right);
            return right;
        }

    }
}
